package com.xw.class11;

import java.util.ArrayList;

/**
 * @author XW
 * @data 2023/8/17 11:05
 * @description 求二叉树某个节点的后继节点（后继节点的含义就是中序遍历后对应位置的后一个节点）
 */
public class Code05_SuccessorNode {
    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     *  方法一 二叉树中序遍历得到数组后，比较得到下一个节点即可
     * @param node 当前节点
     * @return
     */
    public static Node getSuccessorNode1(Node node){
        Node target = null;
        if(node == null ){
            return node;
        }
        Node head = node;
        while (head.parent != null){
            head = head.parent;
        }
        ArrayList<Node> nodes = new ArrayList<>();
        getList(nodes,head);
        if(!nodes.isEmpty()){
            for (int i = 0; i < nodes.size(); i++) {
                Node cur = nodes.get(i);
                if(node.value == cur.value && i+1 < nodes.size()){
                    target = nodes.get(i+1);
                    break;
                }
            }
        }
        return target;
    }
    private static void getList(ArrayList<Node> nodes, Node node) {
        if(node == null){
            return;
        }
        getList(nodes, node.left);
        nodes.add(node);
        getList(nodes,node.right);
    }

    /**
     *  方式二 如果该节点有右子树，找到右子树的最左节点即为该节点的后继节点，如果没有右子树，找当前节点的父节点，如果不是父节点的左孩子，
     *  当前节点更新为父节点，直到当前节点为父节点的左孩子为止，
     * @param node
     * @return
     */
    public static Node getSuccessorNode2(Node node){
        if(null == node){
            return node;
        }
        //有右子树
        if(node.right != null){
            return getTheLeftNode(node.right);
        }else {//无右子树
            Node parent = node.parent;
            while (null != parent && parent.right == node){
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    private static Node getTheLeftNode(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }


    public static void main(String[] args) {
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;

        Node test = head.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value +" * " +  getSuccessorNode2(test).value);
        test = head.left.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.left;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.left.right.right;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.right.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.right.left;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.right;
        System.out.println(test.value + " next: " + getSuccessorNode1(test).value+" * " +  getSuccessorNode2(test).value);
        test = head.right.right; // 10's next is null
        System.out.println(test.value + " next: " + getSuccessorNode1(test)+" * " +  getSuccessorNode2(test).value);
    }
}
